package A1动态规划;

public class LC_115不同的子序列 {
    public int numDistinct(String s, String t) {
        int[][] dp=new int[s.length()+1][t.length()+1];
        for(int i=0;i<s.length();i++)
            dp[i][0]=1;
        for(int j=0;j<t.length();j++)
            dp[0][j]=0;
        dp[0][0]=0;
        char[] cs=s.toCharArray();
        char[] ct=t.toCharArray();
        for(int i=1;i<=s.length();i++)
            for(int j=1;j<=t.length();j++){
                if(cs[i-1]==ct[j-1])
                    dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
                else
                    dp[i][j]=dp[i-1][j];
            }
        return dp[s.length()][t.length()];
    }
}
